package perturbation;

import com.sun.source.tree.WhileLoopTree;
import fundamental.*;

import java.util.*;

import static fundamental.Params.*;
import static initialization.InitialFunction.delayRemove1;
import static initialization.InitialFunction.getNearest;
import static localSearch.LocalSearch.*;

public class Perturb {
    /**
     * 随机选择一个cand移除，随机选择未开放的离该cand最近的几个cand中的一个（是否调用原来的启发式算法重组路径）
     */
    public static void exchangeCand() {
        System.out.println("执行了exchange");
        for (int i = 0; i < perturbLevel; i++) {
            int t = random.nextInt(openedCandSet.size());
            int o = 0;
            Cand removeCand = null;
            for (Cand cand: openedCandSet
            ) {
                if (o == t) {
                    removeCand = cand;
                    break;
                }else o++;
            }
            Cand finalRemoveCand = removeCand;
            PriorityQueue<Cand> minQueue = new PriorityQueue<>(Comparator.comparingDouble(item -> -dist[finalRemoveCand.num][item.num]));
            for (Cand cand: candSet
            ) {
                if (!openedCandSet.contains(cand)) {
                    if (minQueue.size() < aimSize) minQueue.add(cand);
                    else {
                        if (dist[finalRemoveCand.num][minQueue.peek().num] > dist[finalRemoveCand.num][cand.num]) {
                            minQueue.poll();
                            minQueue.add(cand);
                        }
                    }
                }
            }
            if (minQueue.size() == 0)return;
            t = random.nextInt(minQueue.size());
            o = 0;
            Cand aimCand = null;
            while (!minQueue.isEmpty()) {
                if (t == o) {
                    aimCand = minQueue.poll();
                    break;
                }else minQueue.poll();
                o++;
            }
            openedCandSet.remove(removeCand);
            openedCandSet.add(aimCand);
            //aimCand.loading = removeCand.loading;
            //aimCand.overLoading = removeCand.overLoading;
            removeCand.initial();
            System.out.println("移除"+removeCand.num+",移入"+aimCand);
        }


        /*//  这里先采用直接分配的方式过继，即使用新的在一二级路径中代替原来的cand
        for (SecondVehicle v: secondVehicleList
             ) {
            if (v.start_end == removeCand) {
                changeStart_end(v, aimCand);
            }
        }
        for (FirstVehicle v: firstVehicleList
             ) {
            for (int i = 1; i < v.route.size()-1; i++) {
                if (v.route.get(i) == removeCand) {
                    v.route.set(i, aimCand);
                }
            }
        }
        //  重置属性
        removeCand.initial();
        //  重新计算成本
        secCost = getSecCost();
        firCost = getFirCost();*/
    }

    /**
     * 从最近的几个cand中随机选择一个cand移除
     */
    public static void removeCand() {
        System.out.println("执行了remove");
        for (int ignore = 0; ignore < perturbLevel; ignore++) {
            PriorityQueue<Cand[]> minQueue = new PriorityQueue<>(Comparator.comparingDouble(u -> -dist[u[0].num][u[1].num]));
            ArrayList<Cand> openedCandList = new ArrayList<>(openedCandSet);
            for (int i = 0; i < openedCandList.size(); i++) {
                Cand cand1 = openedCandList.get(i);
                for (int j = i+1; j < openedCandList.size(); j++) {
                    Cand cand2 = openedCandList.get(j);
                    if (minQueue.size() < aimSize) {
                        minQueue.add(new Cand[]{cand1, cand2});
                    }else {
                        Cand[] cands = minQueue.peek();
                        if (dist[cand1.num][cand2.num] < dist[cands[0].num][cands[1].num]) {
                            minQueue.poll();
                            minQueue.add(new Cand[]{cand1, cand2});
                        }
                    }
                }
            }
            if (minQueue.size() == 0) continue;
            int t = random.nextInt(minQueue.size());
            Cand removeCand = null;
            int o = 0;
            while (! minQueue.isEmpty()) {
                if (o == t) {
                    Cand[] temp = minQueue.poll();
                    if (random.nextBoolean()) removeCand = temp[0];
                    else removeCand = temp[1];
                    break;
                }
                o++;
            }
            openedCandSet.remove(removeCand);
            removeCand.initial();
            System.out.println("移除的是"+removeCand.num);
        }

        /*//  对于二级路径，计算该路径到其他cand的成本增量，选择最小的加入，并更新cand的loading
        for (SecondVehicle v: secondVehicleList
             ) {
            if (v.start_end == removeCand) {
                double minAddDist = Integer.MAX_VALUE;
                Cand minCand = null;
                for (Cand cand: openedCandSet
                     ) {
                    double d = dist[cand.num][v.route.get(1).num] + dist[v.route.get(v.route.size()-2).num][cand.num];
                    if (d < minAddDist) {
                        minAddDist = d;
                        minCand = cand;
                    }
                }
                changeStart_end(v, minCand);
                for (Point p: v.route
                     ) {
                    if (p instanceof Customer) minCand.loading += ((Customer)p).overDemand;
                }
                minCand.loading += v.loading;
                minCand.flashLoading(cap1);
            }
        }
        //  对于一级路径，删除remove，重新计算所有车的loading，如果超载，则分离车辆
        Cand finalRemoveCand = removeCand;
        int n = firstVehicleList.size();
        for (int i = 0; i < n; i++) {
            FirstVehicle v = firstVehicleList.get(i);
            v.route.removeIf(u -> u == finalRemoveCand);
            v.loading = 0;
            for (Point p : v.route
            ) {
                if (p instanceof Cand) v.loading += ((Cand) p).loading;
            }
            if (v.loading > v.cap) {
                FirstVehicle vc = new FirstVehicle(cap1, vFix1, vvar1);
                vc.start_end = v.start_end;
                vc.add(vc.start_end);
                vc.add(v.route.get(1));
                vc.add(vc.start_end);
                v.loading -= vc.loading;
                v.route.remove(1);
                firstVehicleList.add(vc);
            }
        }
        firCost = getFirCost();
        secCost = getSecCost();*/
    }

    /**
     * 选择距离开放的cand中距离最近的最远的几个cand，随机选择一个cand开放
     */
    public static void addCand() {
        System.out.println("执行add");
        for (int i = 0; i < perturbLevel; i++) {
            //  存放每一个未开放的cand到开放的cand中的最近的距离
            HashMap<Cand, Double> nearestDistMap = new HashMap<>();
            for (Cand cand: candList
            ) {
                if (!openedCandSet.contains(cand)) {
                    for (Cand minCand: candSortForDist.get(cand)
                    ) {
                        if (openedCandSet.contains(minCand)) {
                            double minDist = dist[cand.num][minCand.num];
                            nearestDistMap.put(cand, minDist);
                            break;
                        }
                    }
                }
            }
            PriorityQueue<Cand> queue = new PriorityQueue<>(Comparator.comparingDouble(nearestDistMap::get));
            for (Cand cand: nearestDistMap.keySet()
            ) {
                if (queue.size() < aimSize) queue.add(cand);
                else {
                    Cand temp = queue.peek();
                    if (nearestDistMap.get(cand) < nearestDistMap.get(temp)) {
                        queue.poll();
                        queue.add(temp);
                    }
                }
            }
            if (queue.size() == 0) return;
            int t = random.nextInt(queue.size());
            int o = 0;
            while (o < t) {
                queue.poll();
                o++;
            }
            openedCandSet.add(queue.peek());
            System.out.println("移入"+queue.peek());
        }

    }

    /**
     * 随机选择giantTSP中m对，两两交换位置
     */
    public static void mutateOper1() {
        pairNum = giantTSP.validTour.size()/10;
        int[] index = new int[2*pairNum];
        ArrayList<Integer> tempList = new ArrayList<>();
        for (int i = 0; i < giantTSP.validTour.size(); i++) {
            tempList.add(i);
        }
        for (int i = 0; i < 2*pairNum; i++) {
            int in = random.nextInt(tempList.size());
            index[i] = tempList.get(in);
            tempList.remove(in);
        }
        for (int i = 0; i < index.length; i+=2) {
            Point temp = giantTSP.validTour.get(index[i]);
            giantTSP.validTour.set(index[i], giantTSP.validTour.get(index[i+1]));
            giantTSP.validTour.set(index[i+1], temp);
        }
    }

    /**
     * 随机移除四条最长边中的两条，中间片段将按照成本最小原则插入
     */
    public static void mutateOper2() {
        Queue<Integer> edgeList = new PriorityQueue<>(Comparator.comparingDouble(e -> dist[giantTSP.tour.get(e-1).num][giantTSP.tour.get(e).num]));
        int amount = 4;
        int chooNum = 2;
        for (int i = 1; i < giantTSP.validTour.size(); i++) {
            if (edgeList.size() < amount) {
                edgeList.add(i);
            }else {
                double max = edgeList.peek();
                if (dist[giantTSP.validTour.get(i-1).num][giantTSP.validTour.get(i).num] > max) {
                    edgeList.poll();
                    edgeList.add(i);
                }
            }
        }
        int[] choosed = new int[chooNum];
        ArrayList<Integer> edges = new ArrayList<>(edgeList);
        if (edges.size() < chooNum) return;
        for (int i = 0; i < chooNum; i++) {
            int in = random.nextInt(edges.size());
            choosed[i] = edges.get(in);
            edges.remove(in);
        }
        Arrays.sort(choosed);
        ArrayList<Point> subTour = new ArrayList<>(giantTSP.validTour.subList(0,choosed[0]));
        subTour.addAll(giantTSP.validTour.subList(choosed[1],giantTSP.validTour.size()));
        ArrayList<Point> partial = new ArrayList<>(giantTSP.validTour.subList(choosed[0],choosed[1]));
        double minAdd = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < subTour.size()+1; i++) {
            double adding;
            if (i == 0){
                adding = dist[partial.get(partial.size()-1).num][subTour.get(0).num];
            }else if (i == subTour.size()){
                adding = dist[subTour.get(subTour.size()-1).num][partial.get(0).num];
            }else {
                adding = dist[subTour.get(i-1).num][partial.get(0).num]+dist[partial.get(partial.size()-1).num][subTour.get(i).num]-dist[subTour.get(i-1).num][subTour.get(i).num];
            }
            if (minAdd > adding){
                minAdd = adding;
                minIndex = i;
            }
        }
        giantTSP.validTour.clear();
        giantTSP.validTour.addAll(subTour.subList(0, minIndex));
        giantTSP.validTour.addAll(partial);
        giantTSP.validTour.addAll(subTour.subList(minIndex, subTour.size()));
    }

    /**
     * 将tour变成一个环，随机截断四条最长边中的一条
     */
    public static void mutateOper3() {
        ArrayList<Integer> edgeIndexList = new ArrayList<>();
        for (int i = 0; i < giantTSP.validTour.size(); i++) {
            edgeIndexList.add(i);
        }
        ArrayList<Double> edgeValueList = new ArrayList<>();
        if (giantTSP.validTour.size() == 0) return;
        edgeValueList.add(dist[giantTSP.validTour.get(0).num][giantTSP.validTour.get(giantTSP.validTour.size()-1).num]);
        for (int i = 1; i < giantTSP.validTour.size(); i++) {
            double d = dist[giantTSP.validTour.get(i-1).num][giantTSP.validTour.get(i).num];
            edgeValueList.add(d);
        }
        edgeIndexList.sort(Comparator.comparingDouble(edgeValueList::get));
        if (edgeIndexList.size() < 4) return;
        int bre = edgeIndexList.get(random.nextInt(4));
        ArrayList<Point> list1 = new ArrayList<>(giantTSP.validTour.subList(bre,giantTSP.validTour.size()));
        ArrayList<Point> list2 = new ArrayList<>(giantTSP.validTour.subList(0,bre));
        giantTSP.validTour.clear();
        giantTSP.validTour.addAll(list1);
        giantTSP.validTour.addAll(list2);
    }

    /**
     * 执行三种扰动中的一种
     */
    public static void perturb1(){
        int t = random.nextInt(3);
        if (t == 0) addCand();
        else if (t == 1) exchangeCand();
        else removeCand();
        clearAll();
        giantTSP.getValidTour();
        int num = random.nextInt(3);
        if (num == 0){
            mutateOper1();
        }else if (num == 1){
            mutateOper2();
        }else {
            mutateOper3();
        }
        SPFA();
        pathToRoute();
        secCost = getSecCost();
        getRoute1ByGreedy();
        firCost = getFirCost();
        /*Check.check1();
        Check.check2();
        Check.checkOpenedCand();
        Check.checkTotalDemand();*/
    }

    /**
     * 使用经过优先队列优化的split算法
     */
    public static void SPFA() {
        ArrayList<Point> route = new ArrayList<>();
        route.add(new Customer());
        route.addAll(giantTSP.validTour);
        Queue<Integer> checkList = new LinkedList<>();
        checkList.add(0);
        double[] v = new double[route.size()];
        Arrays.fill(v, Integer.MAX_VALUE);
        int[] p = new int[route.size()];
        Cand[] d = new Cand[route.size()];
        boolean[] used = new boolean[route.size()];
        while (!checkList.isEmpty()) {
            int i = checkList.remove();
            int load = 0;
            double cost;
            double partCost = 0;
            int j = i+1;
            while (j < route.size() && load <= giantTSP.cap2) {
                load += ((Customer) route.get(j)).demand;
                if (j > i+1) {
                    partCost += dist[route.get(j-1).num][route.get(j).num]*vvar2;
                }
                double minCost = Integer.MAX_VALUE;
                Cand sat = null;
                for (Cand cand: openedCandSet
                     ) {
                    double nowCost = (dist[cand.num][route.get(i+1).num]+dist[route.get(j).num][cand.num])*vvar2+partCost;
                    if (minCost >= nowCost){
                        minCost = nowCost;
                        sat =cand;
                    }
                }
                cost = minCost;
                if (load <= giantTSP.cap2) {
                    if (i == 0) {
                        if (cost < v[j]){
                            v[j] = cost;
                            d[j] = sat;
                            p[j] = i;
                            if (! used[j]){
                                checkList.add(j);
                                used[j] = true;
                            }
                        }
                    }
                    else {
                        if (v[i] + cost < v[j]){
                            v[j] = v[i] + cost;
                            p[j] = i;
                            d[j] = sat;
                            if (! used[j]){
                                checkList.add(j);
                                used[j] = true;
                            }
                        }
                    }
                    j += 1;
                }else break;
            }
            used[i] = false;
        }
        int check = route.size()-1;
        while (check > 0) {
            route.add(p[check]+1, d[check]);
            check = p[check];
        }
        route.remove(0);
        giantTSP.path.clear();
        giantTSP.path.addAll(route);
    }

    /**
     * 将用split算法分割的路径转化为第二级路径的标准格式
     */
    public static void pathToRoute() {
        int i = 0;
        while (i < giantTSP.path.size()) {
            if (giantTSP.path.get(i) instanceof Cand) {
                int k = 0;
                for (int j = i+1; j < giantTSP.path.size(); j++) {
                    k = j;
                    if (giantTSP.path.get(j) instanceof Cand) {
                        SecondVehicle sv = new SecondVehicle(cap2, vFix2,vvar2);
                        secondVehicleList.add(sv);
                        sv.start_end = (Cand) giantTSP.path.get(i);
                        sv.route.addAll(giantTSP.path.subList(i,j));
                        sv.route.add(sv.start_end);
                        for (Point p: giantTSP.path.subList(i+1, j)
                             ) {
                            Customer cust = (Customer) p;
                            sv.loading += cust.demand;
                            sv.start_end.loading += (cust.demand+cust.overDemand);
                        }
                        i = j;
                        break;
                    }
                }
                if (k == giantTSP.path.size()-1 && i != giantTSP.path.size()-1) {
                    SecondVehicle sv = new SecondVehicle(cap2, vFix2, vvar2);
                    secondVehicleList.add(sv);
                    sv.start_end = (Cand) giantTSP.path.get(i);
                    sv.route.addAll(giantTSP.path.subList(i,k+1));
                    sv.route.add(sv.start_end);
                    for (Point p: giantTSP.path.subList(i+1, k+1)
                         ) {
                        Customer cust = (Customer) p;
                        sv.loading += cust.demand;
                        sv.start_end.loading += (cust.demand+cust.overDemand);
                    }
                    break;
                }
            }
        }
    }

    /**
     * 采用启发式构造算法中的方法获取第一级路径
     */
    public static void getRoute1ByGreedy() {
        //firstVehicleList.clear();
        //  构造一级路径（在这之前要对cand的loading进行处理），方式同构造一级路径，但是要注意路径长度
        for (Cand cand: openedCandSet
        ) {
            cand.flashLoading(cap1);
        }
        HashMap<Depot, HashSet<Cand>> depotCandMap = new HashMap<>();
        for (Depot depot: depotList
        ) {
            depotCandMap.put(depot, new HashSet<>());
        }
        for (Cand cand: openedCandSet
        ) {
            double minDist = Integer.MAX_VALUE;
            Depot minDepot = null;
            for (Depot depot: depotList
            ) {
                //  这里没必要考虑不生效的5公里
                if (dist[depot.num][cand.num] < minDist) {
                    minDist = dist[depot.num][cand.num];
                    minDepot = depot;
                }
            }
            depotCandMap.get(minDepot).add(cand);
        }
        for (Depot depot: depotCandMap.keySet()
        ) {
            HashSet<Cand> waitCandSet = depotCandMap.get(depot);
            PriorityQueue<Cand> candToDepotQueue = new PriorityQueue<>(Comparator.comparingDouble(o -> dist[o.num][depot.num]));
            candToDepotQueue.addAll(waitCandSet);
            HashSet<Cand> needRemove = new HashSet<>();
            while (!candToDepotQueue.isEmpty()) {
                FirstVehicle v = new FirstVehicle(cap1,vFix1,vvar1);
                v.add(depot);
                v.start_end = depot;
                firstVehicleList.add(v);
                Cand nowCand = candToDepotQueue.poll();
                waitCandSet.remove(nowCand);
                v.add(nowCand);
                while (!waitCandSet.isEmpty() && v.route.size() < 3) {
                    Cand nextCand = getNearest(nowCand, waitCandSet);
                    if (v.cap - v.loading >= nextCand.loading) {
                        v.add(nextCand);
                        needRemove.add(nextCand);
                        waitCandSet.remove(nextCand);
                        nowCand = nextCand;
                    }else break;
                }
                v.add(depot);
                delayRemove1(needRemove, candToDepotQueue);
            }
        }
        secCost = getSecCost();
        firCost = getFirCost();
    }

    public static void clearAll() {
        for (Cand cand: openedCandSet
             ) {
            cand.initial();
        }
        firstVehicleList.clear();
        secondVehicleList.clear();
    }


}
